#include <set>
#include <iostream>

using std::set;
using std::cout;

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int val) : val(val), next(nullptr) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) 
    {
        ListNode* fast = head;
        ListNode* slow = head;
        
        // 找到相遇点
        while(1)
        {
            if(fast == nullptr || fast->next == nullptr) return nullptr;

            fast = fast->next->next;

            slow = slow->next;
            if(fast == slow) break;
        }

        // fast： x + y + n(y + z)
        // slow: x + y
        // x + y = n(y + z)
        // x = n(y + z) - y
        // x = ny - y + nz
        // x = (n - 1)y + nz
        // x = (n - 1)(y + z) + z

        // 找到相遇点
        ListNode* cur = head;
        while (cur != slow)
        {
            cur = cur->next;
            slow = slow->next;
        }
        return cur;
    }
};


